Авторы |
Попков Кирилл Андреевич, младший научный сотрудник, сектор теоретической кибернетики отдела № 4, Федеральный исследовательский центр, Институт прикладной математики имени М. В. Келдыша Российской академии наук (Россия, г. Москва, Миусская площадь, 4), kirill-formulist@mail.ru
|
Аннотация |
Актуальность и цели. Рассматривается задача синтеза неизбыточных схем из функциональных элементов в базисе {&, +, 1, 0} , реализующих булевы функции от n переменных и допускающих короткие единичные диагностические тесты относительно константных неисправностей типа 0 на выходах элементов. Эта задача относится к проблеме синтеза легкотестируемых схем, поставленной С. В. Яблонским и И. А. Чегис в 50-х гг. прошлого века, и к настоящему времени достаточно хорошо изучена.
Материалы и методы. При построении легкотестируемых схем используется ранее известный метод синтеза, модифицированный под данную задачу. Нижние оценки длин тестов доказываются «от противного», путем получения ограничений на структуру схем, допускающих короткие тесты.
Результаты. Для каждой булевой функции найдено минимально возможное значение длины единичного диагностического теста в базисе {&, +, 1, 0} при указанных неисправностях. В частности, доказано, что оно не превосходит двух.
Выводы. Рассмотренная задача решена полностью. В частности, существенно улучшены имевшиеся ранее верхние оценки минимальных длин единичных диагностических тестов в этой постановке задачи.
|
Список литературы |
1. Чегис, И. А. Логические способы контроля работы электрических схем / И. А. Чегис, С. В. Яблонский // Труды Математического института имени В. А. Стеклова. – 1958. – Т. 51. – С. 270–360.
2. Яблонский, С. В. Надежность и контроль управляющих систем / С. В. Яблонский // Материалы Всесоюзного семинара по дискретной математике и ее приложениям. – М. : МГУ, 1986. – С. 7–12.
3. Яблонский, С. В. Некоторые вопросы надежности и контроля управляющих систем / С. В. Яблонский // Математические вопросы кибернетики. – Вып. 1. – М. : Наука, 1988. – С. 5–25.
4. Редькин, Н. П. Надежность и диагностика схем / Н. П. Редькин. – М. : Изд-во МГУ, 1992.
5. Reddy, S. M. Easily testable realization for logic functions / S. M. Reddy // IEEE Trans. Comput. – 1972. – Vol. 21, № 1. – P. 124–141. 6. Коляда, С. С. Верхние оценки длины проверяющих тестов для схем из функциональных элементов : дис. … канд. физ.-мат. наук / Коляда С. С. – М., 2013. – 77 с.
7. Романов, Д. С. Метод синтеза легкотестируемых схем, допускающих единичные проверяющие тесты константной длины / Д. С. Романов // Дискретная математика.–2014.–Т.26,вып.2.–С.100–130.
8. Редькин, Н. П. О полных проверяющих тестах для схем из функциональных элементов / Н. П. Редькин // Вестник Московского университета. Сер. 1. Математика. Механика.–1986.–№1.–С.72–74.
9. Редькин, Н. П. О полных проверяющих тестах для схем из функциональных элементов / Н. П. Редькин // Математические вопросы кибернетики. – Вып. 2. – М. : Наука, 1989. – С. 198–222.
10. Романов, Д. С. О синтезе схем, допускающих полные проверяющие тесты константной длины относительно произвольных константных неисправностей на выходах элементов / Д. С. Романов // Дискретная математика. – 2013. – Т. 25, вып. 2. – С. 104–120.
11. Редькин, Н. П. О схемах, допускающих короткие тесты / Н. П. Редькин // Вестник Московского университета. Сер. 1. Математика. Механика. – 1988. – № 2. – С. 17–21.
12. Редькин, Н. П. О единичных диагностических тестах для однотипных константных неисправностей на выходах функциональных элементов / Н. П. Редькин // Вестник Московского университета. Сер. 1. Математика. Механика. – 1992. – № 5. – С. 43–46.
13. Бородина, Ю. В. О схемах, допускающих единичные тесты длины 1 при кон- стантных неисправностях на выходах элементов / Ю. В. Бородина // Вестник Московского университета. Сер. 1. Математика. Механика. – 2008. – № 5. – С. 49–52.
14. Попков, К. А. О точном значении длины минимального единичного диагностического теста для одного класса схем / К. А. Попков // Препринты ИПМ им. М. В. Келдыша. – 2015. – № 74. – 20 с.
15. Бородина, Ю. В. О синтезе легкотестируемых схем в случае однотипных кон- стантных неисправностей на выходах элементов / Ю. В. Бородина // Вестник Московского университета. Сер. 15. Вычислительная математика и кибернетика. – 2008. – № 1. – С. 40–44.
16. Бородина, Ю. В. Синтез легкотестируемых схем в базисе Жегалкина при константных неисправностях типа 0 на выходах элементов / Ю. В. Бородина, П. А. Бородин // Дискретная математика. – 2010. – Т. 22, вып. 3. – С. 127–133.
17. Угольников, А. Б. Классы Поста : учеб. пособие / А. Б. Угольников. – М. : Изд-во ЦПИ при механико-математическом факультете МГУ, 2008.
|